package leet_code;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;
import java.util.Stack;

/**
 * 链表相关
 */
public class A_7_LinkedList {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 206. 反转链表
     * https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan-v2&envId=top-100-liked
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
     * <p>
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * <p>
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     * <p>
     * 输入：head = []
     * 输出：[]
     * <p>
     * 提示：
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     * <p>
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
     * 83. 删除排序链表中的重复元素
     * https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * <p>
     * 示例 1：
     * 输入：head = [1,1,2]
     * 输出：[1,2]
     * <p>
     * 示例 2：
     * 输入：head = [1,1,2,3,3]
     * 输出：[1,2,3]
     * <p>
     * <p>
     * 提示：
     * 链表中节点数目在范围 [0, 300] 内
     * -100 <= Node.val <= 100
     * 题目数据保证链表已经按升序排列
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 回文
     */
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode p = head;
        while (p != null) {
            stack.push(p.val);
            p = p.next;
        }
        ListNode q = head;
        while (q != null) {
            if (!Objects.equals(q.val, stack.pop())) {
                return false;
            }
            q = q.next;
        }
        return true;
    }

    /**
     * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
     * 实现 LRUCache 类：
     * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
     * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
     *
     * 示例：
     * 输入
     * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
     * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
     * 输出
     * [null, null, null, 1, null, -1, null, -1, 3, 4]
     *
     * 解释
     * LRUCache lRUCache = new LRUCache(2);
     * lRUCache.put(1, 1); // 缓存是 {1=1}
     * lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
     * lRUCache.get(1);    // 返回 1
     * lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
     * lRUCache.get(2);    // 返回 -1 (未找到)
     * lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
     * lRUCache.get(1);    // 返回 -1 (未找到)
     * lRUCache.get(3);    // 返回 3
     * lRUCache.get(4);    // 返回 4
     *
     *
     * 提示：
     * 1 <= capacity <= 3000
     * 0 <= key <= 10000
     * 0 <= value <= 10^5
     * 最多调用 2 * 10^5 次 get 和 put
     * @param args
     */


    /**
     * 排序链表
     * 进阶：在nlogn的时间和空间复杂度内完成
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        //使用归并排序实现
        //1、找到链表的中点，使用快慢指针实现，快：走两步，慢：走一步 快指针到达终点时慢指针即是中点
        //2、对子链表进行排序，自底而上
        //3、合并
        return mergeSort(head);
    }

    public ListNode mergeSort(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        //p前进一，q前进二，分割链表
        while (q != null && q.next != null && p.next != null) {
            //当快指针没办法前进两步时，前进一步
            q = q.next;
            if (q.next == null) {
                break;
            }
            q = q.next;
            p = p.next;
        }
        //只有一个元素
        if (head == q) {
            return head;
        }
        ListNode px = p.next;
        p.next = null;

        //对链表进行继续拆分指最小粒度
        ListNode pSorted = mergeSort(head);
        ListNode qSorted = mergeSort(px);

        //并
        return merge(pSorted, qSorted);
    }

    private ListNode merge(ListNode p, ListNode q) {
        ListNode head = new ListNode();
        ListNode maxNode = head;
        while (p != null && q != null) {
            if (p.val > q.val) {
                maxNode.next = q;
                q = q.next;
            } else {
                maxNode.next = p;
                p = p.next;
            }
            maxNode = maxNode.next;
        }
        maxNode.next = q == null ? p : q;
        return head.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
//        ListNode listNode1 = new ListNode(3);
//        ListNode listNode2 = new ListNode(2);
//        ListNode listNode3 = new ListNode(1);
//
//        listNode.next = listNode1;
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;

        A_7_LinkedList linkedList = new A_7_LinkedList();
//        ListNode listNode5 = linkedList.deleteDuplicates(listNode);
//        boolean palindrome = linkedList.isPalindrome(listNode);

//        while (listNode5 != null) {
//            System.out.println(listNode5.val);
//            listNode5 = listNode5.next;
//        }
//        System.out.println(palindrome);
        ListNode listNode4 = linkedList.mergeSort(listNode);
        while (listNode4 != null) {
            System.out.println(listNode4.val);
            listNode4 = listNode4.next;
        }
    }
}
